﻿#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>

//力扣189

//1.给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。

//例1

//输入: nums = [1, 2, 3, 4, 5, 6, 7], k = 3
//输出 : [5, 6, 7, 1, 2, 3, 4]
//解释 :
//	向右轮转 1 步 : [7, 1, 2, 3, 4, 5, 6]
//	向右轮转 2 步 : [6, 7, 1, 2, 3, 4, 5]
//	向右轮转 3 步 : [5, 6, 7, 1, 2, 3, 4]


//例 2:
//
//输入：nums = [-1, -100, 3, 99], k = 2
//输出：[3, 99, -1, -100]
//解释 :
//	向右轮转 1 步 : [99, -1, -100, 3]
//	向右轮转 2 步 : [3, 99, -1, -100]
//


//第一种方法：暴力求解
//1.将数组最后一位保存起来
//2.将数组其他位向右移位移动
//3.将保存起来的最后一位放到第一位
//以上是右旋一个数，while循环，需要旋转k个就行

//时间复杂度N^2
//旋转一次的时间复杂度是O(N),需要旋转k次，所以是k*N
//当k=1时，时间复杂度是O(N),但时间复杂度要看最坏的情况
//k最坏是N-1,最坏是旋转N-1次, 所以k*N=(N-1)*N=N^2-N
//所以时间复杂度是N^2

//空间复杂度O(1)
//额外开辟了三个空间tmp，i，count，是常数次，所以是O(1)

/*
void rotate(int* nums, int numsSize, int k) 
{
	int tmp = 0;
	int count = 0;
	if(k>numsSize)
	{
		k%=numsSize;
	}
	while (count < k)
	{
		int i = numsSize - 1;
		tmp = nums[i];
		for (i = numsSize-2; i >= 0;i--)
		{
			nums[i + 1] = nums[i];
		}
		nums[0] = tmp;
		count++;
	}
}

int main()
{
	int arr[8] = { 1,2,3,4,5,6,7,8 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	int k = 5;
	rotate(arr, sz, k);
	int i = 0;
	for (i = 0; i < sz; i++)
	{
		printf("%d ", arr[i]);
	}

	return 0;
}
*/


//第二种方法：三段逆置
//1.将前n-k个逆置
//2.将后k个逆置
//3.将整体再逆置

//需要注意的点是
//1.逆置函数reverse函数，需要传函数，需要逆置的数段的左右下标，传下标即可
//2.涉及到旋转的问题，都得判断下，旋转的次数是否超过数组的个数，k和numsSize的关系，如果k>numsSize，那k=k%numsSize
//得处理一下k，不然可能会形成越界访问，比如如果数组是[-1],k=2，这个例子就会有越界访问，所以k得处理一下


//时间复杂度是O(2N)即O(N)
//空间复杂度是O(1)

/*
void reverse(int* nums, int left, int right)
{
	int tmp = 0;
	while (left < right)
	{
		tmp = nums[left];
		nums[left] = nums[right];
		nums[right] = tmp;
		left++;
		right--;
	}
}

void rotate(int* nums, int numsSize, int k)
{
	if (k > numsSize)
	{
		k %= numsSize;
	}
	reverse(nums, 0, numsSize - k - 1);
	reverse(nums, numsSize - k, numsSize- 1);
	reverse(nums, 0, numsSize - 1);

}

int main()
{
	int arr[8] = { 1,2,3,4,5,6,7,8 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	int k = 6;
	rotate(arr, sz, k);
	int i = 0;
	for (i = 0; i < sz; i++)
	{
		printf("%d ", arr[i]);
	}

	return 0;
}

*/


//第三种方法：空间换时间
//1.新开辟一个空间
//2.把需要逆置的k个先拷过去
//3.把剩下的n-k个拷过去
//4.把新开辟的空间复制拷贝到原数组空间

/*
#include<string.h>
#include<stdlib.h>

void rotate(int* nums, int numsSize, int k)
{
	if (k > numsSize)
		k %= numsSize;
	int* tmp = (int*)malloc(sizeof(int)*numsSize);
	memcpy(tmp, nums +numsSize-k, sizeof(int) * k);
	memcpy(tmp+k, nums, sizeof(int) * (numsSize-k));
	memcpy(nums, tmp, sizeof(int) * numsSize);
	free(tmp);
	tmp = NULL;
}

int main()
{
	int arr[8] = { 1,2,3,4,5,6,7,8 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	int k = 7;
	rotate(arr, sz, k);
	int i = 0;
	for (i = 0; i < sz; i++)
	{
		printf("%d ", arr[i]);
	}

	return 0;
}

*/